/**
 * @param {number[]} nums
 * @return {number}
 */
// hash集合：解法1
// 生成一个集合，对数组进行遍历，如果比当前数小1的在集合中，就没必要判断当前数。
// 如果没有，从当前数开始判断，一直+1直到找不到。
var longestConsecutive1 = function(nums) {
    const set = new Set(nums)
    let ans = 1
    for(let i = 0; i < nums.length; i++) {
        let cur = nums[i]
        if(!set.has(cur - 1)) {
            while(set.has(cur + 1)) {
                cur++
            }
        }
        ans = Math.max(ans, cur - nums[i] + 1)
    }
    return ans
};
// 记录每个数字能到达的最远右边界
var longestConsecutive2 = function(nums) {
    const map = new Map()
    for(let n of nums) {
        map.set(n, n); // 最远右边界为自己
    }
    let ans = 0
    for(let n of nums) {
        if(!map.has(n - 1)) { // 没有比自己小的，那从自己开始计算
            let right = map.get(n)
            while(map.has(right + 1)) {
                right = map.get(right + 1)
            }
            map.set(n, right)
            ans = Math.max(ans, right - num + 1)
        }
    }
    return ans
};
console.log(longestConsecutive1([100, 4, 200, 1, 2]));